package demo22;

import java.util.Arrays;

public class Select {
    //选择排序
    public static void main(String[]args){
        int[]array={3,5,1,2,9,7,5,6,4,3,0};

        System.out.println("排序前：");
        System.out.println(Arrays.toString(array));
        selectSort(array);
        System.out.println("排序后");
        System.out.println(Arrays.toString(array));
        System.out.println();
        System.out.println("排序前：");
        int []array2={4,8,2,0,5,3,41,3};
        System.out.println(Arrays.toString(array2));
        selectSort(array2);
        System.out.println("优化排序后");
        System.out.println(Arrays.toString(array2));
    }
    public static void selectSort(int[]array){
        for(int i=0;i< array.length;i++){
            int min=i;
            for(int j=i+1;j< array.length;j++){//找到最小的一个一个的排
                if(array[j]<array[min]){
                    min=j;
                }
            }
            swap(array,i,min);
        }
    }
    public static void swap(int[]array,int i,int j){
        int temp=array[i];
        array[i]=array[j];
        array[j]=temp;
    }
    //选择排序的优化，找到最大值与最小值分别放尾与头，之后left++，right--，继续找第二大的和第二小的放尾与头，如此重复即可
    public void selectSort2(int []array){
        int left=0;
        int right=array.length-1;
        while(left<right){
            int min=left;
            int max=left;
            for(int i=left+1;i<array.length;i++){
                if(array[i]<array[min]){
                    min=i;
                }
                if(array[i]>array[max]){
                    max=i;
                }
            }
            swap(array,left,min);
            if(max==left){
                max=min;//防止最大值为头时，因上一次交换，把头值放在中间，min下标处时，依靠max原值已找不到最大值
            }
            swap(array,right,max);
            right--;
            left++;
        }
    }
}
